# input are two lists of size n, containing either 0 or 1
# output list representation of sum of the lists
def bit_sum(A,B):
    n=len(A)
    C=[0]*(n+1)
    out=0
    for i in xrange(n):
        if A[i]+B[i]+out==0:
            C[i]=0
            out=0
        elif A[i]+B[i]+out==1:
            C[i]=1
            out=0
        elif A[i]+B[i]+out==2:
            C[i]=0
            out=1
        elif A[i]+B[i]+out==3:
            C[i]=1
            out=1
    if out==1:
        C[-1]=1
    return C
        
if __name__=='__main__':
    A=[0,1,0,1,1]
    B=[1,0,1,1,1]
    C=bit_sum(A,B)
    print 'A=', A
    print 'B=', B
    print 'A+B=', C
        
